Many applications in the multimedia and scientific space require fast multi-dimensional search capabilities. At the same time, there is an emergence of commodity hardware with multi-core processors. However, existing algorithms for multi-dimensional searching cannot exploit underlying parallelism and/or are difficult to efficiently port to the various hardware platforms.
Large high-dimensional datasets are becoming ubiquitous. Many applications require the retrieval of data items similar to a given query item, or the nearest neighbors (NN) of a given item. Another common requirement is the retrieval of multi-NN, that is, multiple NN for different query items on the same data. With multi-core central processing units (CPUs) becoming more and more widespread at lower costs, developing parallel algorithms for the above-mentioned exemplary search problems presents additional challenges.